package seqlist.oj;

/**
 * 找到环的入口
 */
public class Num142 {
    public ListNode detectCycle(ListNode head) {
        ListNode low = head,fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
            // 此时low和fast相遇了
            if (low == fast) {
                // 创建一个新node，从头开始和low一起走
                ListNode third = head;
                // 他俩一定会在环的入口位置相遇
                while (third != low) {
                    low = low.next;
                    third = third.next;
                }
                return low;
            }
        }
        return null;
    }
}
